#include <bits/stdc++.h>

#define eb emplace_back
#define ep emplace
#define fi first
#define se second
#define in read<int>()
#define lin read<ll>()
#define rep(i, x, y) for(int i = (x); i <= (y); i++)
#define per(i, x, y) for(int i = (x); i >= (y); i--)

using namespace std;

using ll = long long;
using db = double;
using pii = pair < int, int >;
using vec = vector < int >;
using veg = vector < pii >;

template < typename T > T read() {
	T x = 0; bool f = 0; char ch = getchar();
	while(!isdigit(ch)) f |= ch == '-', ch = getchar();
	while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
	return f ? -x : x;
}

template < typename T > void chkmax(T &x, const T &y) { x = x > y ? x : y; }
template < typename T > void chkmin(T &x, const T &y) { x = x < y ? x : y; }

const int N = 1e3 + 10;

namespace Blossom {
	int n, m, col[N], fa[N], pre[N], mat[N];
	vec G[N];
	int vis[N], tim;
	queue < int > q; 
	void match(int x, int y) { mat[x] = y; mat[y] = x; }
	int gf(int x) { return fa[x] == x ? x : fa[x] = gf(fa[x]); }
	int lca(int x, int y) {
		++tim; x = gf(x), y = gf(y);
		while(vis[x] ^ tim) { vis[x] = tim; x = gf(pre[mat[x]]); if(y) swap(x, y); }
		return x;
	}
	void blossom(int x, int y, int L) {
		while(gf(x) != L) {
			pre[x] = y; y = mat[x]; if(col[y] == 2) q.ep(y), col[y] = 1;
			if(gf(x) == x) fa[x] = L;
			if(gf(y) == y) fa[y] = L;
			x = pre[y];
		}
	}
	bool tmatch(int x) {
		rep(i, 1, n) fa[i] = i, col[i] = 0, pre[i] = 0;
		while(q.size()) q.pop(); q.ep(x); col[x] = 1;
		while(q.size()) {
			int x = q.front(); q.pop();
			for(auto y : G[x]) {
				if(col[y] == 2 || gf(y) == gf(x)) continue;
				if(!col[y]) {
					col[y] = 2; pre[y] = x;
					if(!mat[y]) {
						for(int k = y; k; y = k) k = mat[pre[y]], match(pre[y], y);
						return true;
					}
					col[mat[y]] = 1; q.ep(mat[y]);
				} else { int L = lca(x, y); blossom(x, y, L); blossom(y, x, L); }
			}
		} return false;
	}
	int runit() { int ans = 0; rep(i, 1, n) ans += (!mat[i] && tmatch(i)); return ans; }
}

int n, m;

int main() {
#ifndef ONLINE_JUDGE
	freopen("1.in", "r", stdin);
#endif
	n = in, m = in;
	rep(i, 1, m) { int x = in, y = in; Blossom :: G[x].eb(y); Blossom :: G[y].eb(x); }
	Blossom :: n = n; Blossom :: m = m;
	printf("%d\n", Blossom :: runit());
	rep(i, 1, n) printf("%d ", Blossom :: mat[i]);
	return 0;
}
